<?php
class hash2 {

    public $array;
    private $reallysize;
    private $primetable=array(3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369);

    public function __construct($size){
        $this->reallysize=$this->getPrime($size);
        $this->array = new SplFixedArray($this->reallysize);
    }

    public function Ha($i) {
        return $i%$this->reallysize;
    }
    
    public function isPrime($i){
      if($i&1!=0){//如果是奇数
          $middle=intval($i/2);
          for ($j= 3; $j<=$middle; $j+=2) {
             if($i%$j==0)  return false;             
          }
          return TRUE;
      }
      return ($i==2);  //2是质数里唯一的偶数
        
    }
    //如果 min 是质数，返回 min；否则返回比 min 稍大的那个质数
    public function getPrime($min) {
        //从质数表中查找比 min 稍大的质数
        for ($i = 0; $i < count($this->primetable); $i++) {
            if($this->primetable[$i]>=$min){
                return $this->primetable[$i];
            }
        }
        //min 超过了质数表的范围时，探查 min 之后的每一个奇数，直到发现下一个质数
        for ($i = ($min|1); $i < PHP_INT_MAX; $i+=2) {
            if($this->isPrime($i)) return $i;
        }
        return min;
    }


    public function add($i) {
        if ($this->array[$this->Ha($i)] == null) {
            $linklist = new SplDoublyLinkedList();
            $linklist->push($i);
            $this->array[$this->Ha($i)] = $linklist;
        } else {
            $linklist = $this->array[$this->Ha($i)];
            $linklist->push($i);
        }
    }

    public function contain($i) {
        if ($this->array[$this->Ha($i)] == null) {
            return FALSE;
        } else {
            $linklist = $this->array[$this->Ha($i)];
            $count = $linklist->count();
            for ($j = 0; $j <= $count; $j++) {
                if($linklist->offsetGet($j)==$i){
                    return TRUE;
                }
            }
        }
    }
}
$hashmod=new hash2(20);
var_dump($hashmod->Ha(3));
var_dump($hashmod->Ha(93));
var_dump($hashmod->Ha(45));
$hashmod->add(2);
$hashmod->add(15);
$hashmod->add(12);
var_dump($hashmod->contain(2));
var_dump($hashmod->contain(15));
var_dump($hashmod->contain(12));
?>
